package com.mlh.dp.knapsackProblem;

// 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
// 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
// 你可以认为每种硬币的数量是无限的。
//
// 输入：coins = [1, 2, 5], amount = 11
// 输出：3
// 解释：11 = 5 + 5 + 1

public class CoinChange {

    public static void main(String[] args) {
        int[]coins={186,419,83,408};
        method1(coins,6249);
    }

    //思路：完全背包  由于物品是无数量限制的
    //因此应该将背包容量作为外循环  物品作为内循环（每个都选一遍）
    //再来就是注意起始条件
    public static int method1(int[] coins, int amount) {
        int[]dp=new int[amount+1];
            for(int i=1;i<=amount;i++){
                dp[i]=Integer.MAX_VALUE>>1;
                for(int j=0;j<coins.length;j++){
                    if(i>=coins[j]){
                        dp[i]= Math.min(dp[i-coins[j]]+1,dp[i]) ;
                    }
                }
            }
            if(dp[amount]>100000){
                return -1;
            }
            return dp[amount];
    }
}
